home *** CD-ROM | disk | FTP | other *** search
/ Aminet 7 / Aminet 7 - August 1995.iso / Aminet / docs / misc / ConcNews.lha / news / general.programming / comp.programming_2202_000027.msg < prev    next >
Encoding:
Text File  |  1994-11-27  |  1.6 KB  |  38 lines
  1. Newsgroups: comp.programming
  2. Path: dd.chalmers.se!news.chalmers.se!sunic!EU.net!sun4nl!baby!jos
  3. From: jos@and.nl (Jos Horsmeier)
  4. Subject: Re: Conservative Sorting/Presv Order of Orig??
  5. Message-ID: <Cor54w.2Jx@and.nl>
  6. Keywords: sort heap conservative
  7. Organization: AND Software B.V., Rotterdam
  8. References: <ConxHx.KHv@acsu.buffalo.edu>
  9. Date: Sun, 24 Apr 1994 07:07:43 GMT
  10. Lines: 26
  11.  
  12. In article <ConxHx.KHv@acsu.buffalo.edu> cudmore@acsu.buffalo.edu (Robert H. Cudmore) writes:
  13.  
  14. |    I am attempting to sort an array of elements A.  I have a Heap sort
  15. |up and running, the problem is this:  I need the elements with equal keys
  16. |to remain in their original order.  Heap sort with building(hiring) and 
  17. |Sorting(firing) of the array into a heap and then into a sorted array seems
  18. |to cause the destruction of the original order of all elements. 
  19. |
  20. |    Are there efficient O(nlogn) sorting routines that will preserve this
  21. |original order?  Quicksort seems to do the same destructive ordering of
  22. |the data where as a simple insertion sort does not.  I would like to stay
  23. |away from linear complexity sorts and would also like to know if I can't
  24. |stay away from them.
  25.  
  26. A cheap trick: for all elements A_1, A_2, ..., A_n add an integer tag
  27. field to those records and initialize them with the values i for all A_i.
  28. If two keys compare equal, compare the tag fields. That's all there is
  29. to it. No two keys will compare equal in this case ...
  30.  
  31. I hope this helps you out,
  32.  
  33. kind regards,
  34.  
  35. Jos aka jos@and.nl
  36. ----------------------------------------------------------------------------
  37. I'm not hooked on nicotine, it's that I just can't do without it.
  38.